

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-04-29
 * Time: 13:32
 */
public class AvlTree {
    static class TreeNode{
        public int val;
        public int bf;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public TreeNode(int val){
            this.val = val;
        }
    }
    private TreeNode root;
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root==null){
            root = node;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur!=null){
            if(cur.val<val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val==val){
                return false;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
     if(parent.val < val){
         parent.right = node;
     }else{
         parent.left = node;

     }
     cur = node;
     parent = cur.parent;
     while(parent!=null){
         if(cur == parent.right){
             parent.bf ++;
         }else{
             parent.bf--;
         }



         if(parent.bf==0){
             break;
         }else if(parent.bf==1 || parent.bf==-1){
             cur = parent;
             parent =parent.parent;
         }else{
             if(parent.bf==2){
                 if(cur.bf==1){
                     //左单旋
                   rotateLeft(parent);
                 }else{
                     //cur.bf==-1;
                     //右左双旋
                   //  rotateRL(parent);
                 }
             }else{
                //parent.bf==-2
                 if(cur.bf==1){
                     //左右双旋
                     rotateLR(parent);

                 }else{
                     //cur.bf==-1;
                     //右单旋
                     rotateRight(parent);
                 }
             }
         }
     }
     return true;
    }

    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRl = subR.left;
        if(subRl != null){
            subRl.parent = parent;
        }

       TreeNode pParent = parent.parent;
        parent.parent  = subR;
        subR.left = parent;
        parent.right = subRl;
        parent.bf = 0;
        subR.bf = 0;
        if(parent==root){
            root = subR;
            subR.parent = null;
        }else{
            if(parent==pParent.left){
                subR.parent = pParent;
                pParent.left = parent;
            }else {
                subR.parent =pParent;
                pParent.right = subR;
            }
        }
    }
    public void rotateRight(TreeNode parent){
        TreeNode subL=parent.left;
        TreeNode subLR = subL.right;
        subL.right = parent;
        parent.left = subLR;
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        if(subLR!=null){
            subLR.parent = parent;
        }
        if(parent==root){
            root = subL;
            root.parent=null;
        }else{
            if(parent==pParent.left){
                subL.parent = pParent;
               pParent.left = subL;
            }else{
                subL.parent = pParent;
                 pParent.right = subL;
            }
            subL.bf = 0;
            parent.bf =0;
        }



    }
    public void rotateLR(TreeNode parent){

    }

    public static void main(String[] args) {

    }
}
